<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>二叉搜索树查询路径</title>
    <script src="https://d3js.org/d3.v7.min.js"></script>
    <style>
        .node {
            fill: lightblue;
            stroke: black;
            stroke-width: 1.5px;
            cursor: pointer;
        }

        .link {
            fill: none;
            stroke: #ccc;
            stroke-width: 2px;
        }

        .clicked {
            fill: orange;
        }

        .error {
            fill: red;
        }

        #message {
            font-size: 20px;
            font-weight: bold;
            margin-top: 20px;
        }

        #path {
            font-size: 16px;
            font-weight: bold;
            margin-top: 10px;
        }
    </style>
</head>
<body>
<h1>请选择查询 <span id="random-node-name"></span> 的路径</h1>
<svg width="600" height="400"></svg>
<div id="message"></div>
<div id="path">正确路径：<span id="correct-path"></span></div>

<script>
    // Function to generate a Binary Search Tree (BST)
    function insert(root, name) {
        if (root === null) {
            return { name: name, left: null, right: null };
        }

        if (name < root.name) {
            root.left = insert(root.left, name);
        } else if (name > root.name) {
            root.right = insert(root.right, name);
        }

        return root;
    }

    // Function to generate a random Binary Search Tree (BST)
    function generateRandomBST(minNodes, maxNodes) {
        let root = null;
        const values = Array.from({ length: maxNodes - minNodes + 1 }, (_, i) => i + minNodes);

        // Shuffle the values to get random inserts
        for (let i = values.length - 1; i > 0; i--) {
            const j = Math.floor(Math.random() * (i + 1));
            [values[i], values[j]] = [values[j], values[i]];
        }

        // Insert values into BST
        values.forEach(value => {
            root = insert(root, value);
        });

        return root;
    }

    // Function to convert BST node to d3.hierarchy node
    function convertToD3Hierarchy(node) {
        if (!node) return { name: null, children: [] };
        // Convert the BST structure to D3's expected hierarchy structure
        return {
            name: node.name,
            children: [
                convertToD3Hierarchy(node.left),
                convertToD3Hierarchy(node.right)
            ]
        };
    }

    // Generate a random BST with 10-15 nodes
    let treeData = generateRandomBST(1, 15);

    // Convert the BST into a format that D3 expects
    const d3TreeData = convertToD3Hierarchy(treeData);

    // Find the path from root to a given target node
    function findPathToNode(root, target, path = []) {
        if (!root) return null;

        // Add the current node to the path
        path.push(root.name);

        // If the current node is the target, return the path
        if (root.name === target) {
            return path;
        }

        // Recursively search in left or right subtree
        const leftPath = findPathToNode(root.children[0], target, path.slice());
        if (leftPath) return leftPath;

        const rightPath = findPathToNode(root.children[1], target, path.slice());
        return rightPath;
    }

    // Randomly select a target node from the tree
    const allNodes = [];
    function collectNodes(node) {
        if (!node) return;
        if (node.name !== null) allNodes.push(node.name);
        if (node.children) {
            node.children.forEach(collectNodes);
        }
    }
    collectNodes(d3TreeData);

    // Pick a random node from the tree
    const randomNodeName = allNodes[Math.floor(Math.random() * allNodes.length)];
    document.getElementById("random-node-name").innerText = randomNodeName;

    // Find the path to the randomly selected node
    const correctDFSSequence = findPathToNode(d3TreeData, randomNodeName);

    // Display the correct DFS sequence on the page
    document.getElementById("correct-path").innerText = correctDFSSequence.join(" -> ");

    let userClickIndex = 0;

    // Set up the SVG canvas dimensions
    const width = 600;
    const height = 400;

    const svg = d3.select("svg");

    // Create a tree layout
    const treeLayout = d3.tree().size([width - 100, height - 100]);

    // Create the tree structure from the data
    const root = d3.hierarchy(d3TreeData);
    treeLayout(root);

    // Create the links (edges)
    svg.selectAll(".link")
        .data(root.links())
        .enter().filter(d => d.source.data.name !== null && d.target.data.name !== null)
        .append("line")
        .attr("class", "link")
        .attr("x1", d => d.source.x + 50)
        .attr("y1", d => d.source.y + 50)
        .attr("x2", d => d.target.x + 50)
        .attr("y2", d => d.target.y + 50);

    // Create the nodes (elements)
    const nodes = svg.selectAll(".node")
        .data(root.descendants())
        .enter().filter(d => d.data.name !== null)
        .append("circle")
        .attr("class", "node")
        .attr("cx", d => d.x + 50)
        .attr("cy", d => d.y + 50)
        .attr("r", 20)
        .on("click", function(event, d) {
            handleNodeClick(d);
        });

    // Add labels to nodes
    svg.selectAll(".label")
        .data(root.descendants())
        .enter()
        .append("text")
        .attr("x", d => d.x + 50)
        .attr("y", d => d.y + 50)
        .attr("dy", 5)
        .attr("text-anchor", "middle")
        .text(d => d.data.name);

    // Handle node click event
    function handleNodeClick(node) {
        const clickedNodeName = node.data.name;

        if (clickedNodeName === correctDFSSequence[userClickIndex]) {
            // Correct click
            d3.select(event.target)  // Use event.target instead of node
                .classed("clicked", true);
            userClickIndex++;
            showMessage("正确，继续点击后续节点");
            if (userClickIndex === correctDFSSequence.length) {
                showMessage("成功，查询顺序正确！");
            }
        } else {
            // Incorrect click
            d3.select(event.target)  // Use event.target instead of node
                .classed("error", true);
            userClickIndex = 0;
            showMessage("错误，请重新开始！");
        }
    }

    // Display message
    function showMessage(message) {
        document.getElementById("message").innerText = message;
    }
</script>
</body>
</html>
